
package day1;

/**
 * 
 * 题目描述：
 * 1. 给定一个含有n个元素的整型数组array，其中只有一个元素出现奇数次，找出这个元素
 * 2. 由n个元素组成的数组，n-2个数出现了偶数次，两个数出现了奇数次（这两个数不相等），找出这个两个元素
 * 
 * 解题思路：
 * 1. 通过使用异或操作来选择出现奇数次数的数据。具体原理为：a^b^a=a^a^b=0^b=b,即相同位异或为0，不同位异或为1到原理。
 * 当某数出现奇次时，通过异或运算一定可以保存下来。
 * 2. 首先第一遍异或运算即可获取到x=a^b, 同时根据第一轮的异或可以判断出a和b一定有某一位相反，一个为0另一个为1，
 * 此时，使用一个变量y进行x&（～x+1）则一定可以获取到那个为1的位，通过这个变量在和数组进行与的操作，即可获取到a
 * 或者b，然后在使用x^y即可获取到另一个数。
 */
public class FindElementWithOddCount {

    public static void main(String[] args) {
        int[] test1 = new int[5];
        test1[0] = 2;
        test1[1] = 2;
        test1[2] = 6;
        test1[3] = 6;
        test1[4] = 1;
        findElementWithOddCountOne(test1);

        int[] test2 = new int[10];
        test2[0] = 1;
        test2[1] = 2;
        test2[2] = 6;
        test2[3] = 6;
        test2[4] = 2;
        test2[5] = 8;
        test2[6] = 5;
        test2[7] = 5;
        test2[8] = 8;
        test2[9] = 9;
        findElementWithOddCountTwo(test2);
    }

    public static void findElementWithOddCountOne(int[] array) {
        int result = 0;
        for (int i = 0; i < array.length; i++) {
            result ^= array[i];
        }
        System.out.println("数组中出现奇数次数的数据为:" + result);
    }

    public static void findElementWithOddCountTwo(int[] array) {
        int resultA = 0;
        // 获取到a^b
        for (int i = 0; i < array.length; i++) {
            resultA ^= array[i];
        }

        // resultA中必然有一位是1
        int rightOne= resultA & (~resultA + 1);//取出最右位的1
        int resultB = 0;
        for (int j = 0; j < array.length; j++) {
            // 此时数据可以分成两组：一类与高位运算为0、一类与高位运算为rightOne
            if ((rightOne & array[j]) == 0) {
                System.out.print("j="+j+" ");
                // 此时在过滤一遍与最高位运算为0的这些数据，将出现偶数次的数据过滤掉，
                // 即a^b^a=b
                resultB ^= array[j];
            }
            // 最终resultB为a、b其中某一个
        }
        // 另一个值则也可以得出
        // resultA = resultA ^ resultB;
        System.out.println("数组中出现奇数次数的数据为:a=" + (resultA^resultB) + ",b=" + resultB);
    }

}